package main

import "fmt"

func main() {
	root := &TreeNode{Value: 10}
	values := []int{5, 15, 3, 7, 12, 18}
	for _, value := range values {
		root.insert(value)
	}

	fmt.Println("In-order traversal of the binary search tree:")
	root.inorderTraversal()

	fmt.Println("Search for value 7 in the tree:")
	result := root.search(7)
	if result != nil {
		fmt.Println("Found:", result.Value)
	} else {
		fmt.Println("Not found")
	}
}

// 二叉搜索树（Binary Search Tree, BST）：对于每个节点，左子树的所有节点值小于该节点值，右子树的所有节点值大于该节点值。
type TreeNode struct {
	Left  *TreeNode
	Value int
	Right *TreeNode
}

func (n *TreeNode) insert(value int) {
	if n == nil {
		return
		// 如果当前插入的值,小于当前节点的
	} else if value < n.Value {
		if n.Left == nil {
			n.Left = &TreeNode{
				Value: value,
			}
		} else {
			n.Left.insert(value)
		}
		// 如果大于当前节点
	} else {
		if n.Right == nil {
			n.Right = &TreeNode{Value: value}
		} else {
			n.Right.insert(value)
		}
	}
}

func (n *TreeNode) search(value int) *TreeNode {
	if n.Value == value || n == nil {
		return n
	} else if value < n.Value {
		return n.Left.search(value)
	} else {
		return n.Right.search(value)
	}
}

func (n *TreeNode) inorderTraversal() {
	if n != nil {
		n.Left.inorderTraversal()
		fmt.Println(n.Value)
		n.Right.inorderTraversal()
	}

}
